Trong lý thuyết thông tin: sự sai lệch các đoạn mã và ký tự

Với lượng thông tin khổng lồ được truyền qua điện thoại, Internet hay từ vệ tinh ngoài không gian đến Trái Đất,... Điều này cực kỳ quan trọng nếu đảm bảo sự nguyên vẹn của thông tin khi nhận được.[5]

Khoảng cách Hamming

Khoảng cách Hamming là cái tên được đặt theo tên của Richard Hamming, người giới thiệu lý thuyết này trong tài liệu có tính cơ sở của ông về mã phát hiện lỗi và sửa lỗi (error-detecting and error-correcting codes). Nó được sử dụng trong kỹ thuật viễn thông để tính số lượng các bit trong một từ nhị phân (binary word) bị đổi ngược, như một hình thức để ước tính số lỗi xảy ra trong quá trình truyền thông, và vì thế, đôi khi, nó còn được gọi là khoảng cách tín hiệu (signal distance). Việc phân tích trọng lượng Hamming của các bit còn được sử dụng trong một số ngành, bao gồm lý thuyết tin học, lý thuyết mã hóa, và mật mã học. Tuy vậy, khi so sánh các dãy ký tự có chiều dài khác nhau, hay các dãy ký tự có xu hướng không chỉ bị thay thế đi, mà còn bị ảnh hưởng bởi dữ liệu bị chèn thêm vào, hoặc bị xóa đi, phương pháp đo đạc phức tạp hơn.

Trong lý thuyết thông tin, khi một thông tin được chuyển đi, ví dụ như khi gửi 1 tin nhắn, giả sử nó được mã hóa dưới dạng nhị phân gồm hữu hạn các dãy ký tự 0,1. n phần tử như vậy được gọi là 1 từ có chiều dài n. Mỗi từ có chiều dài n như vậy có thể xem như một vector có chiều dài n gồm toàn bộ các ký tự chỉ chứa những số 0 và 1. Tập tất cả các ký tự như vậy được viết là V n = { ( a 1 , a 2 , . . . , a n ) | a i ∈ { 0 , 1 } , 1 ≤ i ≤ n } {\displaystyle V^{n}=\left\{\left(a_{1},a_{2},...,a_{n}\right)|\;a_{i}\in \left\{0,1\right\},1\leq i\leq n\right\}} . Do đó V n {\displaystyle V^{n}} là tích của n cặp { 0 , 1 } {\displaystyle \left\{0,1\right\}} .

Định nghĩa một metric giữa 2 từ trên tập này là số các vị trí mà tại đó chúng khác nhau.

Metric này được gọi là khoảng cách Hamming.

Ký hiệu là D H a m ( ⋅ , ⋅ ) {\displaystyle D_{Ham}\left(\cdot ,\cdot \right)}

Ví dụ: Cho 2 đoạn mã nhị phân

a = ( 0 , 0 , 1 , 1 , 0 , 1 , 0 , 0 , 1 ) {\displaystyle a=\left(0,0,1,1,0,1,0,0,1\right)} và

b = ( 0 , 1 , 1 , 0 , 0 , 1 , 0 , 0 , 0 ) {\displaystyle b=\left(0,1,1,0,0,1,0,0,0\right)} .

Theo trên a , b {\displaystyle a,b} khác nhau ở các vị trí thứ 2,4 và 9 nên D H a m ( a , b ) = 3 {\displaystyle D_{Ham}\left(a,b\right)=3}

Đối với trình tự ADN (DNA Sequence) và trong khoa học máy tính

Như đã trình bày ở mục trên: "khi so sánh các dãy ký tự có chiều dài khác nhau, hay các dãy ký tự có xu hướng thay thế, mất, chèn,... phức tạp hơn, như khoảng cách Levenshtein (Levenshtein distance) là một phương pháp có tác dụng và thích hợp hơn."

Ngoài ra, trong các thuật toán của bộ môn khoa học máy tính, khái niệm khoảng cách Levenshtein thể hiện khoảng cách khác biệt giữa 2 chuỗi ký tự. Khoảng cách này được đặt theo tên Vladimir Levenshtein, người đã đề ra khái niệm này vào năm 1965. Nó được sử dụng trong việc tính toán sự giống và khác nhau giữa 2 chuỗi, như chương trình kiểm tra lỗi chính tả của winword spellchecker.

Khoảng cách Levenshtein

Khoảng cách Levenshtein giữa dãy x và y xác định bởi: D L ( x , y ) = min S { i S + d S + r S } {\displaystyle D_{L}(x,y)=\min _{S}\lbrace {i_{S}+d_{S}+r_{S}\rbrace }}

Trong đó:

i S {\displaystyle i_{S}} (insertions in sequence) đại diện cho số các phần tử chèn vào trong dãy. d S {\displaystyle d_{S}} (deletions in sequence) đại diện cho số phần tử bị xóa đi. r S {\displaystyle r_{S}} (replacements in sequence) chỉ số những vị trí bị thay thế.

Ví dụ

Tính khoảng cách Levenshtein giữa 2 dãy DNA sau:

X= AGTTCGAATCC, Y=AGCTCAGGAATC

Với X= AGTTCGAATCC

Thay thế T: {\displaystyle \;} AGCTCGAATCCThêm vào A: AGCTCAGAATCCThêm vào G: AGCTCAGGAATCCXóa đi C: {\displaystyle \qquad } AGCTCAGGAATC

Do đó, số tối thiểu các phép chèn, xoá đi và thay thế để biến đổi X thành Y hay khoảng cách Levenshtein giữa X và Y là:

D L ( X , Y ) = min S { i S + d S + r S } = 1 + 2 + 1 = 4 {\displaystyle D_{L}(X,Y)=\min _{S}\lbrace {i_{S}+d_{S}+r_{S}\rbrace }=1+2+1=4}